1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
\r
2 <!-- saved from url=(0053)http://www.ibilce.unesp.br/courseware/datas/data5.htm -->
\r
3 <HTML><HEAD><TITLE>Stacks, Queues, Lists and Hash Tables</TITLE>
\r
4 <META content="Tue, 25 Apr 1995 09:30:00 -0700" http-equiv=Expires>
\r
5 <META content="text/html; charset=iso-8859-1" http-equiv=Content-Type>
\r
6 <META content="MSHTML 5.00.2314.1000" name=GENERATOR></HEAD>
\r
7 <BODY bgColor=#ffffff>
\r
8 <P align=center><!--webbot bot="ImageMap" startspan
\r
9 rectangle=" (284,4) (328, 20) onlinet.htm"
\r
10 rectangle=" (231,4) (277, 19) cstart.htm"
\r
11 rectangle=" (158,4) (223, 19) mailto:brian.brown@cit.ac.nz"
\r
12 rectangle=" (55,4) (153, 20) ../default.htm##_top"
\r
13 rectangle=" (6,3) (51, 19) default.htm##_top"
\r
14 src="images/dsmenu.gif" alt="Menu bar" border="0" width="334"
\r
15 height="22" ismap --><MAP name=FrontPageMap0><AREA coords=284,4,328,20
\r
16 href="http://www.ibilce.unesp.br/courseware/datas/onlinet.htm"
\r
17 shape=RECT><AREA coords=231,4,277,19
\r
18 href="http://www.ibilce.unesp.br/courseware/datas/cstart.htm" shape=RECT><AREA
\r
19 coords=158,4,223,19 href="mailto:brian.brown@cit.ac.nz" shape=RECT><AREA
\r
20 coords=55,4,153,20 href="http://www.ibilce.unesp.br/courseware/default.htm"
\r
21 shape=RECT target=_top><AREA coords=6,3,51,19
\r
22 href="http://www.ibilce.unesp.br/courseware/datas/default.htm" shape=RECT
\r
23 target=_top></MAP><IMG alt="Menu bar" border=0 height=22 isMap
\r
24 src="Stacks, Queues, Lists and Hash Tables_archivos/dsmenu.gif"
\r
25 useMap=#FrontPageMap0 width=334><!--webbot bot="ImageMap"
\r
26 i-checksum="35063" endspan --><BR><FONT color=#0000ff size=5>Data Structures
\r
27 And Number Systems</FONT><FONT color=#000000 size=4><BR></FONT><FONT
\r
28 color=#000000 size=3><B>© Copyright Brian Brown, 1984-1999. All rights
\r
29 reserved.</B></FONT></P>
\r
30 <P align=center>Part 5<BR><A
\r
31 href="http://www.ibilce.unesp.br/courseware/datas/default.htm"><IMG alt=index
\r
32 border=0 height=20 src="Stacks, Queues, Lists and Hash Tables_archivos/menu.gif"
\r
34 href="http://www.ibilce.unesp.br/courseware/datas/data4.htm"><IMG alt=prev
\r
36 src="Stacks, Queues, Lists and Hash Tables_archivos/previous.gif" width=60></A>
\r
40 <P><A name=stacks></A></P>
\r
41 <P><B>STACKS</B><BR>A stack is used to provide temporary storage space for
\r
42 values. It is defined as a data structure which operates on a <B>first in, last
\r
43 out</B> basis. Its uses a single pointer (index) to keep track of the
\r
44 information in the stack. </P>
\r
45 <P>The basic operations associated with a stack are, </P>
\r
47 <LI>insert (push) an item onto the stack
\r
48 <LI>remove (pop) an item from the stack </LI></UL>
\r
49 <P>The following diagram shows an empty stack of four locations. It looks just
\r
50 like an array, and it has an index pointer pointing to the beginning of the
\r
51 stack (called the <B>TOP</B> of the stack). </P><PRE><FONT face=fixedsys size=3>
\r
53 | | <------- Stack Pointer
\r
63 <P><B>Pushing items onto the stack</B><BR>The stack pointer is considered to be
\r
64 pointing to a free (empty) slot in the stack. A push operation thus involves
\r
65 copying data into the empty slot of the stack, then adjusting the stack pointer
\r
66 to point to the next free slot. </P><PRE><FONT face=fixedsys size=3>
\r
68 stack[stack_pointer] = data;
\r
69 stack_pointer = stack_pointer + 1;
\r
73 <P>Lets push the value 45 onto the stack. [Note: The stack could hold any data
\r
74 type, not necessarily decimal numbers. We have used numbers for simplicity]. The
\r
75 stack now looks like </P><PRE><FONT face=fixedsys size=3>
\r
79 | | <------- Stack Pointer
\r
87 <P>Note how the stack pointer has been adjusted to point to the next free
\r
88 location in the stack. [Note: for the time being we are ignoring certain
\r
89 problems. We will address these shortly!!!]. </P>
\r
90 <P><B>Removing items from the stack</B><BR>To remove an item, first decrement
\r
91 (subtract 1 from) the stack pointer, then extract the data from that position in
\r
92 the stack. </P><PRE><FONT face=fixedsys size=3>
\r
94 stack_pointer = stack_pointer - 1;
\r
95 data = stack[stack_pointer];
\r
99 <P><B>Time now to address the problems of the above implementation</B><BR>There
\r
100 are a number of problems associated with the above routines for pushing and
\r
101 removing items. </P>
\r
103 <LI>the push module does not check to see if the stack is full
\r
104 <LI>the remove module does not check to see if the stack is empty </LI></UL>
\r
105 <P>There are a number of solutions to this problem. We shall present a
\r
106 simplified solution. We do not argue that it is the best, just that it is one of
\r
107 a possible number of solutions. </P><PRE><FONT face=fixedsys size=3>
\r
108 Comment: Assume that the array elements begin at 1
\r
109 Comment: Assume that the maximum elements of the stack is MAX
\r
111 Var: stack[MAX] : Integer;
\r
118 if stack_pointer >= MAX then
\r
121 stack[stack_pointer] = data;
\r
122 stack_pointer = stack_pointer + 1;
\r
127 if stack_pointer <= 1 then
\r
130 stack_pointer = stack_pointer - 1;
\r
131 data = stack[stack_pointer];
\r
138 <P><A name=queues></A></P>
\r
139 <P><B>QUEUES</B><BR>Everybody has experience with queues as they are common
\r
140 place. Queues occur in cafeterias, petrol stations, shopping centres, anyplace
\r
141 where many people (customers) line up for few resources (cashier's, salespeople,
\r
142 petrol pumps etc). </P>
\r
143 <P>The purpose of a queue is to provide some form of buffering. Typical uses of
\r
144 queues in computer systems are, </P>
\r
146 <LI>process management
\r
147 <LI>buffer between the fast computer and a slow printer </LI></UL>
\r
148 <P>A queue is defined as a data structure which holds a series of items to be
\r
149 processed on a <B>first in first out</B> basis (though some queues can be sorted
\r
150 in priority). The operations associated with a queue are, </P>
\r
152 <LI>initialize the queue
\r
153 <LI>insert an item in the queue
\r
154 <LI>remove an item from the queue
\r
155 <LI>count the number of empty slots in the queue
\r
156 <LI>count the number of items in the queue </LI></UL>
\r
157 <P>The following diagram shows an empty queue. It is identified as a series of
\r
158 ten locations, and two pointers named <B>front</B> and <B>rear</B>. These two
\r
159 pointers keep track of where the front and rear of the queue is. </P><PRE><FONT face=fixedsys size=3>
\r
160 1 2 3 4 5 6 7 8 9 10
\r
161 +---+---+---+---+---+---+---+---+---+---+
\r
162 | | | | | | | | | | |
\r
163 +---+---+---+---+---+---+---+---+---+---+
\r
172 <P>The front pointer is used to delete items, and the rear pointer insert items.
\r
173 Inserting two items called A and B will rearrange the queue to look like, </P><PRE><FONT face=fixedsys size=3>
\r
174 1 2 3 4 5 6 7 8 9 10
\r
175 +---+---+---+---+---+---+---+---+---+---+
\r
176 | A | B | | | | | | | | |
\r
177 +---+---+---+---+---+---+---+---+---+---+
\r
186 <P>The pseudo-code for the various queue operations follows. </P><PRE><FONT face=fixedsys size=3>
\r
190 rear = size of queue
\r
191 end module initialize
\r
194 if count = size of queue
\r
195 queue is full and do not insert
\r
200 if rear > size of queue
\r
203 insert data at queue[rear]
\r
209 queue is empty and do not remove
\r
212 data = queue[front]
\r
215 if front > size of queue
\r
226 return queue.size - count
\r
227 end module free_space
\r
231 <P>The implementation of this is left to the student as a programming exercise.
\r
235 <P><A name=linkedlists></A></P>
\r
236 <P><B>LINKED LISTS</B><BR>Data structures can be arranged in memory in a variety
\r
237 of different ways. Each method has advantages and disadvantages. Arrays for
\r
238 example seem easy to use, where each element is stored sequentially in memory.
\r
240 <P>This type of approach is not efficient in larger computer systems, where a
\r
241 number of users share main memory. In such circumstances, there may not be
\r
242 enough contiguous main memory left to hold a sequentially stored data structure
\r
243 like an array (but there could be enough if all the small free blocks were moved
\r
244 into one large block). </P>
\r
245 <P>One way to overcome this is to link all elements of data together. Data is
\r
246 arranged into records, and a special item is added to each record called a
\r
247 pointer (a link field), which contains a link to the next record etc. Renaming
\r
248 each record as a node and we have a complex data structure called a<B> linked
\r
250 <P>A linked list is a series of nodes connected together via pointers.
\r
251 Pictorially, it looks like, </P><PRE><FONT face=fixedsys size=3>
\r
252 Node 1 +---+ Node 2 +---+ Node n
\r
253 +--------+--+ | +--------+--+ | +--------+--+
\r
254 | | ------+ | | ------+ | | |
\r
255 +--------+--+ +--------+--+ +--------+--+
\r
256 Data Link Data Lnk Data Lnk
\r
259 <P>In Pascal, a node definition looks like, </P><PRE><FONT face=fixedsys size=3>
\r
262 data : string[20];
\r
267 <P>The following Pascal program declares three nodes, inserts data into each of
\r
268 them, then using a pointer, cycles through the chain from node to node printing
\r
269 out the contents of each node. The value 0 is always stored in the last node of
\r
270 a chain, to indicate the end of the list. </P><PRE><FONT face=fixedsys size=3>
\r
271 program linked_list;
\r
274 data : string[20];
\r
278 node1, node2, node3 : node;
\r
281 node1.data := 'Welcome ';
\r
282 node1.next := @node2;
\r
283 node2.data := 'to ';
\r
284 node2.next := @node3;
\r
285 node3.data := 'Linked Lists.';
\r
286 node3.next := nil;
\r
287 nodeptr := @node1;
\r
288 while nodeptr <> nil do
\r
290 write( nodeptr^.data );
\r
291 nodeptr := nodeptr^.next;
\r
297 <P>Linked lists are used in a wide variety of applications. </P>
\r
299 <LI>directory structures
\r
300 <LI>operating systems for process management
\r
301 <LI>data management in data base systems. </LI></UL>
\r
302 <P>An advantage of storing data using a linked list is that the key sequence can
\r
303 be altered by changing the pointers, not by moving data nodes. This means
\r
304 sorting data is quick, but searching is slower as you must follow the chain from
\r
308 <P><A name=hashing></A></P>
\r
309 <P><B>HASHING</B><BR>Hashing is a technique used to improve data access times.
\r
310 Rather than sorting the data according to a key, it computes the location of the
\r
311 data from the key. In simple terms, it computes an <B>index value from the
\r
312 key</B> of the desired record. At that index value, the record is
\r
313 stored/retrieved. </P>
\r
314 <P>If we had an array of 1000 elements, we would expect our hash function (the
\r
315 method used to calculate the index value) to evenly distribute the keys over
\r
316 this range. In practice this is difficult to achieve. It is possible that two
\r
317 different search keys might generate the same hash value (ie, index), and we
\r
318 call this a <B>collision</B>. </P>
\r
319 <P>The size of the table (array) is generally a prime number, as this has the
\r
320 least probability of creating collisions. </P>
\r
321 <P>The following code segment defines an array of records in Pascal which will
\r
322 be used to demonstrate hashing. </P><PRE><FONT face=fixedsys size=3>
\r
324 type data = record
\r
325 name : string[20];
\r
328 hashtable = array[1..size] of data;
\r
331 <P>Next, lets initialize the table with zero's, so this makes it easy to see if
\r
332 information is already stored at a particular element (important when inserting
\r
333 data later). </P><PRE><FONT face=fixedsys size=3>
\r
334 procedure initialize ( var Table : hashtable );
\r
337 for i := 1 to size do
\r
339 Table[i].name := ' ';
\r
340 Table[i].age := 0;
\r
345 <P>The procedure insert will take the hash value and the data and insert it into
\r
346 the table. If the position is already occupied (ie, a collision occurs) the
\r
347 table will be searched from that point onwards till an empty slot occurs. </P><PRE><FONT face=fixedsys size=3>
\r
348 procedure insert ( Position : integer; Element : data ; var Table : hashtable );
\r
350 while Table[Position].name[1] <> ' ' do
\r
351 Position := (Position + 1) mod size;
\r
352 Table[Position] := Element;
\r
356 <P>The procedure hash will generate a hash value from a given data record. In
\r
357 deciding this, it must generate a value between 1 and 511. Obviously, we cannot
\r
358 use the age field of the record, this will generate too many collisions. The
\r
359 best method is to add up the value of all the characters in the persons name,
\r
360 then extract nine bits from it (2^9 = 512) to generate the index value. </P><PRE><FONT face=fixedsys size=3>
\r
361 procedure hash ( var Position : integer ; Element : data ; var Table : hashtable );
\r
366 while i < 20 do
\r
367 position := position + ord(Element.name[i]);
\r
368 position := position mod 511;
\r
372 <P>The remaining procedures to search and delete are left as a programming
\r
373 exercise for the student. <BR></P>
\r
376 <P><B>INDEXED SEQUENTIAL</B><BR>This method seeks to make a direct access file
\r
377 appear like a sequence file. The sequencing is achieved via an index table,
\r
378 which holds the keys of the records and their position within the file. </P>
\r
379 <P>A program reads the index sequentially, and when it locates the key it
\r
380 desires, it reads the record from the indicated position. </P>
\r
381 <P>The advantages of this method are, </P>
\r
383 <LI>the records need not be in key sequence
\r
384 <LI>the records may be processed sequentially or directly </LI></UL>
\r
387 <P><B>FILE MERGING</B><BR>This is the process of merging two or more input files
\r
388 into a single output file (which are normally all sequential in nature). The
\r
389 files to be merged are first sorted using the same key sequence, which is
\r
390 preserved in the output file. </P>
\r
391 <P>A pseudo-code example for a 2-way merge is shown below. </P><PRE><FONT face=fixedsys size=3>
\r
392 program two_way merge
\r
394 read 1st record of infile1, name as rec1
\r
395 read 1st record of infile2, name as rec2
\r
396 while rec1 or rec2 is not an end-of-record
\r
398 if rec1.key < rec2.key
\r
400 write rec1 to outfile
\r
401 read new rec1 from infile1
\r
405 write rec2 to outfile
\r
406 read new rec2 from infile2
\r
410 write end-of-record to outfile
\r
411 end program two_way merge
\r
416 <P align=center><A
\r
417 href="http://www.ibilce.unesp.br/courseware/datas/default.htm"><IMG alt=index
\r
418 border=0 height=20 src="Stacks, Queues, Lists and Hash Tables_archivos/menu.gif"
\r
420 href="http://www.ibilce.unesp.br/courseware/datas/data4.htm"><IMG alt=prev
\r
421 border=0 height=20
\r
422 src="Stacks, Queues, Lists and Hash Tables_archivos/previous.gif" width=60></A>
\r
424 <P align=center><A
\r
425 href="http://www.ibilce.unesp.br/courseware/datas/default.htm" target=_top><FONT
\r
426 size=2>Home</FONT></A><FONT size=2> | </FONT><A
\r
427 href="http://www.ibilce.unesp.br/courseware/default.htm" target=_top><FONT
\r
428 size=2>Other Courses</FONT></A><FONT size=2> | </FONT><A
\r
429 href="mailto:brian.brown@cit.ac.nz"><FONT size=2>Feedback</FONT></A><FONT
\r
430 size=2> | </FONT><A
\r
431 href="http://www.ibilce.unesp.br/courseware/datas/cstart.htm"><FONT
\r
432 size=2>Notes</FONT></A><FONT size=2> | </FONT><A
\r
433 href="http://www.ibilce.unesp.br/courseware/datas/onlinet.htm"><FONT
\r
434 size=2>Tests</FONT></A><FONT size=2> </FONT></P>
\r
435 <P align=center>© Copyright Brian Brown, 1984-1999. All rights
\r
436 reserved.<BR></P></BODY></HTML>
\r
projects / z.facultad / 75.40 / 2do-cuat / material.git / blob